"""
https://leetcode.cn/problems/reconstruct-itinerary
"""

from collections import defaultdict
import heapq
from typing import List


class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = defaultdict(list)
        for u, v in tickets:
            graph[u].append(v)
        for paths in graph.values():
            heapq.heapify(paths)

        stack = []
        def dfs(u):
            paths = graph[u]
            while paths:
                v = heapq.heappop(paths)
                dfs(v)
            stack.append(u)
        dfs("JFK")
        return stack[::-1]
